Computers function by operating on data in accordance with executed instructions. In traditional computer architectures, instructions to be executed are loaded from particular locations in the computer's memory to the computer's central processing unit ("CPU") in a sequence in part determined by the instructions themselves. Unless otherwise directed, the CPU steps through the memory locations in order, executing instructions located in subsequent contiguous locations one after another.
However, certain instructions can cause the CPU to redirect execution to a non-contiguous location determined by the instruction. These "branch" instructions may be conditional or unconditional. In advanced processing units, including those that contain instruction "pipelines," the processor can calculate the target address of an unconditional branch instruction, initiate pre-fetching of the target instruction and continue to fill the pipeline.
Conditional branching is more complicated. A conditional branch is only taken if a specified condition is satisfied, then program execution branches to a non-contiguous location. If the condition is not satisfied, then program execution flow simply "falls through" to the next instruction.
An example of a branch instruction is the assembly language level "jump" instruction. Jump instructions allow the CPU to skip from location to location within the computer's memory, executing instructions at those locations and lending a degree of programming freedom. Jump instructions include an operand designating a location to which to jump. As mentioned above, jumps can be unconditional or conditioned on the existence of a particular state within the computer (i.e., conditional branching).
A conditional jump instruction not only includes an operand designating the location to which to jump but also includes a designation of the state to monitor to determine whether the jump should be taken. This designation is typically made part of the instruction operator. Thus, the general form for a jump instruction in assembly language is "Jxx yyyyy", where "xx" is the state designation and "yyyyyy" is the location in memory to which to jump if xx is satisfied. Additionally, "yyyyyy" may be a label instead of an actual location in memory.
Non-sequential execution of code is less desirable than sequential execution. This is because branching instructions, particularly conditional branching instructions, require more processor time to obtain and jump to the next non-sequential instruction than is required by a program instruction which simply "falls through" to the next sequential instruction. This is also true of a conditional branching instruction where the condition is not satisfied and the branch is not taken. In such a case, program flow falls through to the next sequential instruction after the conditional branch instruction.
Sequential instructions, including conditional branches where the condition is not met, execute faster because the processor needs only to increment its internal program counter in order to obtain the address of the next instruction. In the case of non-sequential execution, including conditional branches where the branch condition is met, the program must first fetch the target address of the next address and then jump to the target address to obtain the next instruction.
Accordingly there is a need in the art for methods of minimizing the number of branch instructions in a program and, in particular, for methods of organizing and selecting instructions in a manner that minimizes the number of times in which execution of a conditional branch results in non-sequential code execution. There is a further need in the art for code optimizers and compilers that can reorder and modify instructions in order to eliminate or minimize non-sequential "taken" branches during program execution.